
<!DOCTYPE html>
<html lang="zh-Hans" class="loading">
<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <meta name="viewport" content="width=device-width, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no">
    <title>每日一道算法题-有效的括号 - Luis Blog</title>
    <meta name="apple-mobile-web-app-capable" content="yes" />
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="google" content="notranslate" />
    <meta name="keywords" content="Luis,"> 
    <meta name="description" content="java开发工程师，喜欢代码，喜欢技术,题目描述给定一个只包括 &amp;#39;(&amp;#39;，&amp;#39;)&amp;#39;，&amp;#39;{&amp;#39;，&amp;#39;}&amp;#39;，&amp;#39;[&amp;#39;，&amp;#39;]&amp;#39; 的字符串，判断字符串是否有效。,"> 
    <meta name="author" content="winter chen"> 
    <link rel="alternative" href="atom.xml" title="Luis Blog" type="application/atom+xml"> 
    <link rel="icon" href="/img/favicon.png"> 
    
    
<link rel="stylesheet" href="/css/diaspora.css">

	<script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
    <script>
         (adsbygoogle = window.adsbygoogle || []).push({
              google_ad_client: "ca-pub-8691406134231910",
              enable_page_level_ads: true
         });
    </script>
    <script async custom-element="amp-auto-ads"
        src="https://cdn.ampproject.org/v0/amp-auto-ads-0.1.js">
    </script>
<meta name="generator" content="Hexo 4.2.0"></head>

<body class="loading">
    <span id="config-title" style="display:none">Luis Blog</span>
    <div id="loader"></div>
    <div id="single">
    <div id="top" style="display: block;">
    <div class="bar" style="width: 0;"></div>
    <a class="iconfont icon-home image-icon" href="javascript:;" data-url="https://blog.winterchen.com"></a>
    <div title="播放/暂停" class="iconfont icon-play"></div>
    <h3 class="subtitle">每日一道算法题-有效的括号</h3>
    <div class="social">
        <div>
            <div class="share">
                <a title="获取二维码" class="iconfont icon-scan" href="javascript:;"></a>
            </div>
            <div id="qr"></div>
        </div>
    </div>
    <div class="scrollbar"></div>
</div>

    <div class="section">
        <div class="article">
    <div class='main'>
        <h1 class="title">每日一道算法题-有效的括号</h1>
        <div class="stuff">
            <span>十月 08, 2019</span>
            
  <ul class="post-tags-list" itemprop="keywords"><li class="post-tags-list-item"><a class="post-tags-list-link" href="/tags/%E7%AE%97%E6%B3%95/" rel="tag">算法</a></li></ul>


        </div>
        <div class="content markdown">
            <h3 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h3><p>给定一个只包括 <code>&#39;(&#39;，&#39;)&#39;，&#39;{&#39;，&#39;}&#39;，&#39;[&#39;，&#39;]&#39;</code> 的字符串，判断字符串是否有效。</p>
<p>有效字符串需满足：</p>
<pre><code>左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。</code></pre><p>注意空字符串可被认为是有效字符串。</p>
<p>示例 1:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: &quot;()&quot;</span><br><span class="line">输出: true</span><br></pre></td></tr></table></figure>
<p>示例 2:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: &quot;()[]&#123;&#125;&quot;</span><br><span class="line">输出: true</span><br></pre></td></tr></table></figure>
<p>示例 3:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: &quot;(]&quot;</span><br><span class="line">输出: false</span><br></pre></td></tr></table></figure>
<p>示例 4:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: &quot;([)]&quot;</span><br><span class="line">输出: false</span><br></pre></td></tr></table></figure>
<p>示例 5:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: &quot;&#123;[]&#125;&quot;</span><br><span class="line">输出: true</span><br></pre></td></tr></table></figure>

<h3 id="解题思路"><a href="#解题思路" class="headerlink" title="解题思路"></a>解题思路</h3><ul>
<li>使用stack</li>
<li>遍历字符串</li>
<li>如果当前字符为左半边括号是，则将其压入栈中</li>
<li>如果是右括号时，分类讨论：<ul>
<li>如栈不为空且为对应的左半边括号，则取出栈顶元素，继续循环</li>
<li>若此时栈为空，则直接返回false</li>
<li>若不为对应的左半边括号，返回false</li>
</ul>
</li>
</ul>
<p><img src="https://raw.githubusercontent.com/azl397985856/leetcode/master/assets/20.validParentheses.gif" alt="图解"></p>
<h3 id="示例代码"><a href="#示例代码" class="headerlink" title="示例代码"></a>示例代码</h3><h4 id="java"><a href="#java" class="headerlink" title="java"></a>java</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">boolean</span> <span class="title">isValid</span><span class="params">(String s)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (!StringUtils.hasText(s)) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        Stack&lt;Character&gt; stack = <span class="keyword">new</span> Stack&lt;&gt;();<span class="comment">//定义一个stack</span></span><br><span class="line">        <span class="keyword">char</span>[] chars = s.toCharArray();</span><br><span class="line">        Map&lt;Character, Character&gt; map = <span class="keyword">new</span> HashMap&lt;&gt;();<span class="comment">//hash表</span></span><br><span class="line">        map.put(<span class="string">'('</span>,<span class="string">')'</span>);</span><br><span class="line">        map.put(<span class="string">'['</span>,<span class="string">']'</span>);</span><br><span class="line">        map.put(<span class="string">'&#123;'</span>,<span class="string">'&#125;'</span>);</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">char</span> aChar : chars) &#123;</span><br><span class="line">            <span class="comment">// 如果是左半边括号，则压入栈</span></span><br><span class="line">            <span class="keyword">if</span> (map.containsKey(aChar))&#123;</span><br><span class="line">                stack.push(aChar);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;<span class="comment">// 不是左半边括号</span></span><br><span class="line">                <span class="comment">// 只有栈中有左半边才有效</span></span><br><span class="line">                <span class="keyword">if</span> (stack.size() != <span class="number">0</span>)&#123;</span><br><span class="line">                    <span class="comment">// 出栈</span></span><br><span class="line">                    Character pop = stack.pop();</span><br><span class="line">                    <span class="comment">// 如果右半边与左半边无法对应则返回false</span></span><br><span class="line">                    <span class="keyword">if</span> (!map.get(pop).equals(aChar))&#123;</span><br><span class="line">                        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">                    &#125;<span class="keyword">else</span> &#123;<span class="comment">// 继续循环</span></span><br><span class="line">                        <span class="keyword">continue</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 左半边括号全部出栈表示两边对应上</span></span><br><span class="line">        <span class="keyword">return</span> stack.isEmpty();</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<h4 id="js"><a href="#js" class="headerlink" title="js"></a>js</h4><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">var</span> isValid = <span class="function"><span class="keyword">function</span>(<span class="params">s</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> valid = <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">const</span> stack = [];</span><br><span class="line">    <span class="keyword">const</span> mapper = &#123;</span><br><span class="line">        <span class="string">'&#123;'</span>: <span class="string">"&#125;"</span>,</span><br><span class="line">        <span class="string">"["</span>: <span class="string">"]"</span>,</span><br><span class="line">        <span class="string">"("</span>: <span class="string">")"</span></span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i <span class="keyword">in</span> s) &#123;</span><br><span class="line">        <span class="keyword">const</span> v = s[i];</span><br><span class="line">        <span class="keyword">if</span> ([<span class="string">'('</span>, <span class="string">'['</span>, <span class="string">'&#123;'</span>].indexOf(v) &gt; <span class="number">-1</span>) &#123;</span><br><span class="line">            stack.push(v);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">const</span> peak = stack.pop();</span><br><span class="line">            <span class="keyword">if</span> (v !== mapper[peak]) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (stack.length &gt; <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> valid;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="python"><a href="#python" class="headerlink" title="python"></a>python</h4><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span>:</span></span><br><span class="line">       <span class="function"><span class="keyword">def</span> <span class="title">isValid</span><span class="params">(self,s)</span>:</span></span><br><span class="line">         stack = []</span><br><span class="line">         map = &#123;</span><br><span class="line">           <span class="string">"&#123;"</span>:<span class="string">"&#125;"</span>,</span><br><span class="line">           <span class="string">"["</span>:<span class="string">"]"</span>,</span><br><span class="line">           <span class="string">"("</span>:<span class="string">")"</span></span><br><span class="line">         &#125;</span><br><span class="line">         <span class="keyword">for</span> x <span class="keyword">in</span> s:</span><br><span class="line">           <span class="keyword">if</span> x <span class="keyword">in</span> map:</span><br><span class="line">             stack.append(map[x])</span><br><span class="line">           <span class="keyword">else</span>:</span><br><span class="line">             <span class="keyword">if</span> len(stack)!=<span class="number">0</span>:</span><br><span class="line">               top_element = stack.pop()</span><br><span class="line">               <span class="keyword">if</span> x != top_element:</span><br><span class="line">                 <span class="keyword">return</span> <span class="literal">False</span></span><br><span class="line">               <span class="keyword">else</span>:</span><br><span class="line">                 <span class="keyword">continue</span></span><br><span class="line">             <span class="keyword">else</span>:</span><br><span class="line">               <span class="keyword">return</span> <span class="literal">False</span></span><br><span class="line">         <span class="keyword">return</span> len(stack) == <span class="number">0</span></span><br></pre></td></tr></table></figure>

<h3 id="扩展"><a href="#扩展" class="headerlink" title="扩展"></a>扩展</h3><p>以上的代码只能针对左右完全对应上，并且中间不能出现任何字符，所以这里我想拓展一下，就像代码中一样，括号能对应上并且中间有代码；</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">boolean</span> <span class="title">isValid</span><span class="params">(String s)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (!StringUtils.hasText(s)) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        Stack&lt;Character&gt; stack = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">        <span class="keyword">char</span>[] chars = s.toCharArray();</span><br><span class="line">        Map&lt;Character, Character&gt; map = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">        map.put(<span class="string">'('</span>,<span class="string">')'</span>);</span><br><span class="line">        map.put(<span class="string">'['</span>,<span class="string">']'</span>);</span><br><span class="line">        map.put(<span class="string">'&#123;'</span>,<span class="string">'&#125;'</span>);</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">char</span> aChar : chars) &#123;</span><br><span class="line">            <span class="keyword">if</span> (map.containsKey(aChar))&#123;</span><br><span class="line">                stack.push(aChar);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">if</span> (stack.size() != <span class="number">0</span> &amp;&amp; map.containsValue(aChar))&#123;</span><br><span class="line">                    Character pop = stack.pop();</span><br><span class="line">                    <span class="keyword">if</span> (!map.get(pop).equals(aChar))&#123;</span><br><span class="line">                        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">                    &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                        <span class="keyword">continue</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> stack.isEmpty();</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<p>输入：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">&quot;&#123;[(234)]&#125;&quot;</span><br></pre></td></tr></table></figure>

<p>输出：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">true</span><br></pre></td></tr></table></figure>
            <!--[if lt IE 9]><script>document.createElement('audio');</script><![endif]-->
            <audio id="audio" loop="1" preload="auto" controls="controls" data-autoplay="false">
                <source type="audio/mpeg" src="">
            </audio>
            
                <ul id="audio-list" style="display:none">
                    
                        
                            <li title='0' data-url='https://raw.githubusercontent.com/WinterChenS/imgrpo/master/mp3/%E6%96%B0%E8%A3%A4%E5%AD%90-%E7%94%9F%E6%B4%BB%E5%9B%A0%E4%BD%A0%E8%80%8C%E7%81%AB%E7%83%AD.mp3'></li>
                        
                    
                </ul>
            
        </div>
        
    <div id='gitalk-container' class="comment link"
		data-enable='false'
        data-ae='false'
        data-ci='77f2adc33e0112d086d7'
        data-cs='e926aa3a621556609b2c2b76d89320fa524e23cd'
        data-r='WinterChenS.github.io'
        data-o='WinterChenS'
        data-a='WinterChenS'
        data-d='false'
    >查看评论</div>


    </div>
    
</div>


    </div>
</div>
</body>


<script src="//lib.baomitu.com/jquery/1.8.3/jquery.min.js"></script>
<script src="/js/plugin.js"></script>
<script src="/js/typed.js"></script>
<script src="/js/diaspora.js"></script>


<link rel="stylesheet" href="/photoswipe/photoswipe.css">
<link rel="stylesheet" href="/photoswipe/default-skin/default-skin.css">


<script src="/photoswipe/photoswipe.min.js"></script>
<script src="/photoswipe/photoswipe-ui-default.min.js"></script>


<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">
    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>
    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">
        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>
        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">
            <div class="pswp__top-bar">
                <!--  Controls are self-explanatory. Order can be changed. -->
                <div class="pswp__counter"></div>
                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
                <button class="pswp__button pswp__button--share" title="Share"></button>
                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                      <div class="pswp__preloader__cut">
                        <div class="pswp__preloader__donut"></div>
                      </div>
                    </div>
                </div>
            </div>
            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div> 
            </div>
            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>
            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>
            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>
        </div>
    </div>
</div>





<!-- Google Analytics -->
<script type="text/javascript">
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

  ga('create', 'G-30C04D6TMS', 'auto');
  ga('send', 'pageview');
</script>
<!-- End Google Analytics -->


</html>
